package com.my.study.structures.linkedlist.josephus;

import lombok.extern.slf4j.Slf4j;

/**
 * @author Carlos
 * @version 1.0
 * @Description TODO
 * @date 2021/6/10 23:46
 **/
@Slf4j(topic = "c.CircleSingleLinkedList")
public class CircleSingleLinkedList {
    /**
     * 创建一个first节点
     */
    private Boy first;

    public void addBoys(int nums) {
        // 校验nums
        if (nums < 1) {
            return;
        }
        // 帮助构建环形链表
        Boy cur = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                cur = first;
            } else {
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            }
        }
    }


    /**
     * 数小孩
     *
     * @param startBoy 开始数的小孩编号
     * @param countNum 数几次出小孩
     * @param nums 小孩个数
     */
    public void countBoy(int startBoy, int countNum, int nums) {
        // 校验
        if (first == null || startBoy < 1 || startBoy > nums) {
            log.debug("参数输入有误，请重新输入");
            throw new RuntimeException("");
        }

        // 初始化helper并将其指向最后一个小孩
        Boy helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }
        // 小孩报数之前，移动到 k - 1次
        for (int i = 0; i < startBoy - 1; i++) {
            first = first.next;
            helper = helper.next;
        }

        while (helper != first) {
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            // 这是first是要出圈的
            System.out.printf("小孩%d出圈", first.getNo());
            first = first.next;
            helper.next = first;
        }
        System.out.printf("最后留在圈中的小孩编号%d", first.getNo());

    }


    public void list() {
        if (first == null) {
            log.debug("链表为空");
            return;
        }
        Boy cur = first;
        while (true) {
            log.debug("当前小孩编号为 {}", cur.getNo());
            if (cur.getNext() == first) {
                break;
            }
            // 后移
            cur = cur.getNext();
        }
    }

    static class Boy {
        /**
         * 编号
         */
        private int no;

        /**
         * 指向下一个节点
         */
        private Boy next;

        public Boy(int no) {
            this.no = no;
        }

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public Boy getNext() {
            return next;
        }

        public void setNext(Boy next) {
            this.next = next;
        }
    }
}
